# 斐波那契数列
a = 20


# 时间复杂度：O(2^n)
def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)


print('斐波那契数列')
for a in range(1, a + 1):
    print(fib(a), end=' ')

print('\n备忘录优化递归')
# 备忘录优化递归
book = [0 for i in range(0, 21)]


# 时间复杂度：O(n)
def helper(n):
    if n == 1 or n == 2:
        return 1
    elif book[n] != 0:
        return book[n]
    else:
        return fib(n - 1) + fib(n - 2)


for a in range(1, a + 1):
    print(helper(a), end=' ')

# dp数组的迭代解法
dp = [0 for i in range(0, 20 + 1)]
# base case
dp[1] = dp[2] = 1


def fib3(n):
    if n == 1 or n == 2:
        return 1

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]


print('\ndp数组的迭代解法')
for a in range(1, a + 1):
    print(fib3(a), end=' ')


# 当前状态只和之前的两个状态有关，其实并不需要那么⻓
# 的⼀个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就⾏
# 了。所以，可以进⼀步优化，把空间复杂度降为 O(1)
def fib4(n):
    if n == 1 or n == 2:
        return 1
    prev, curr = 1, 1
    for i in range(3, n + 1):
        sum_ = prev + curr
        prev = curr
        curr = sum_

    return curr


print('\ndp table 优化 %d' % fib4(20))
